{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "10. 正则表达式匹配\n",
    "给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。\n",
    "\n",
    "'.' 匹配任意单个字符\n",
    "'*' 匹配零个或多个前面的那一个元素\n",
    "所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。\n",
    "\n",
    "说明:\n",
    "\n",
    "s 可能为空，且只包含从 a-z 的小写字母。\n",
    "p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 回溯法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先考虑只有 `.` 这种情况"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if not s and not p:\n",
    "            return True\n",
    "        if not s:\n",
    "            return False\n",
    "        if not p:\n",
    "            return False\n",
    "        if s[0] == p[0]:  \n",
    "            return self.isMatch(s[1:], p[1:])\n",
    "        elif p[0] == \".\":\n",
    "            return self.isMatch(s[1:], p[1:])\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 别人写的\n",
    "class Solution:\n",
    "    def isMatch(self, s: str, p: str) -> bool:\n",
    "        if not p: return not s\n",
    "        # 第一个字母是否匹配\n",
    "        first_match = bool(s and p[0] in {s[0],'.'})\n",
    "        # 如果 p 第二个字母是 *\n",
    "        if len(p) >= 2 and p[1] == \"*\":\n",
    "            return self.isMatch(s, p[2:]) or \\\n",
    "            first_match and self.isMatch(s[1:], p)\n",
    "        else:\n",
    "            return first_match and self.isMatch(s[1:], p[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}